package 力扣.队列;

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class NodeTree{
    int val;
    NodeTree left;
    NodeTree right;
    NodeTree next;
    NodeTree(){}
    NodeTree(int val){
        this.val = val;
    }
    public NodeTree(int val, NodeTree left, NodeTree right, NodeTree next) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }

}
public class 链式二叉树 {
    public static void main(String[] args) {
        NodeTree root = new NodeTree(3);
        NodeTree root2 = new NodeTree(9);
        NodeTree root22 = new NodeTree(8);
        NodeTree root3 = new NodeTree(6);
        NodeTree root33 = new NodeTree(7);

        root.next = null;root.left = root2;root.right = root22;
        root2.next = root22;root2.left = null;root2.right = null;
        root22.next = null;root22.left = root3;root22.right = root33;
        root3.next = root33;
        List<List<Integer>> leveltraversal = leveltraversal(root);
        System.out.println(leveltraversal);
    }

    /**
     * 因为有一个next指针，所有我们每一次只需‘找到每一层中的第一个节点’就可以遍历整层中所有的节点
     * @param root
     * @return
     */
    public static List<List<Integer>> leveltraversal(NodeTree root){
        List<List<Integer>> ans = new ArrayList<>();
        while (root != null){//遍历一层
            List<Integer> tes = new ArrayList<>();
            NodeTree root2 = null;
            while (root != null){//遍历一层的所有节点
                if (root2 == null){//找到下一层的第一个节点
                    if (root.left != null){
                        root2 = root.left;
                    }else if (root.right != null){
                        root2 = root.right;
                    }
                }
                tes.add(root.val);
                root = root.next;//向右遍历
            }
            ans.add(tes);
            root = root2;
        }
        return ans;
    }
}
